package com.cat.greedyAlgorithm;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-deletions-to-make-string-k-special/description/
 * @create 2025/10/10 17:49
 * @since JDK17
 */

public class Solution74 {
    public int minimumDeletions(String word, int k) {
        int[] cnt = new int[26];
        int ans = Integer.MAX_VALUE, right = 0;
        for (var c : word.toCharArray()) {
            cnt[c - 'a']++;
        }
        Arrays.sort(cnt);
        int sum = Arrays.stream(cnt).sum(), h;
        for (int i = 25; i >= 0 && cnt[i] > 0; i--) {   //
            sum -= cnt[i];
            h = 0;
            for (int j = 25; j > i; j--) {
                h += Math.max(cnt[j] - cnt[i] - k, 0);
            }
            ans = Math.min(ans, sum + h);
        }

        return ans;
    }
}
